package codeRandomThoughts.Test236二叉树的最近公共祖先;

import codeRandomThoughts.utils.TreeNode;

public class Solution2 {
    /**
     * 思路1:回溯法求出到两个节点的路径,然后求重合的部分
     * 思路2:利用数组存储二叉树的性质,父节点所在位置为(当前节点下标+1)/2 - 1
     * 思路3:后序遍历
     */
    private TreeNode ancestor;

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        ancestor = root;
        postorder(root, p, q);
        return ancestor;
    }

    public boolean postorder(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return false;

        //后序遍历
        //左
        boolean left = postorder(root.left, p, q);

        //右
        boolean right = postorder(root.right, p, q);

        //根
        if (left && right || (left || right) && (root == p || root == q)) ancestor = root;
        if (root == p || root == q) return true;
        return left || right;
    }
}
